<?xml version="1.0" encoding="iso-8859-1"?>
<!DOCTYPE html
    PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<!-- ../src/examples/mandelbrot.qdoc -->
<head>
  <title>Mandelbrot Example</title>
    <style type="text/css">h3.fn,span.fn { margin-left: 1cm; text-indent: -1cm; }
a:link { color: #004faf; text-decoration: none }
a:visited { color: #672967; text-decoration: none }
td.postheader { font-family: sans-serif }
tr.address { font-family: sans-serif }
body { color: black; }</style>
</head>
<body>
<h1 class="title">Mandelbrot Example<br /><span class="subtitle"></span>
</h1>
<p>The Mandelbrot example shows how to use a worker thread to perform heavy computations without blocking the main thread's event loop.</p>
<p>The heavy computation here is the Mandelbrot set, probably the world's most famous fractal. These days, while sophisticated programs such as <a href="http://xaos.sourceforge.net/">XaoS</a> that provide real-time zooming in the Mandelbrot set, the standard Mandelbrot algorithm is just slow enough for our purposes.</p>
<p align="center"><img src="classpath:com/trolltech/images/mandelbrot.png" alt="Screenshot of the Mandelbrot example" /></p><p>In real life, the approach described here is applicable to a large set of problems, including synchronous network I/O and database access, where the user interface must remain responsive while some heavy operation is taking place.</p>
<p>The Mandelbrot application supports zooming and scrolling using the mouse or the keyboard. To avoid freezing the main thread's event loop (and, as a consequence, the application's user interface), we put all the fractal computation in a separate worker thread. The thread emits a signal when it is done rendering the fractal.</p>
<p>During the time where the worker thread is recomputing the fractal to reflect the new zoom factor position, the main thread simply scales the previously rendered pixmap to provide immediate feedback. The result doesn't look as good as what the worker thread eventually ends up providing, but at least it makes the application more responsive. The sequence of screenshots below shows the original image, the scaled image, and the rerendered image.</p>
<p><table align="center" cellpadding="2" cellspacing="1" border="0">
<tr valign="top" class="odd"><td><img src="classpath:com/trolltech/images/mandelbrot_zoom1.png" /></td><td><img src="classpath:com/trolltech/images/mandelbrot_zoom2.png" /></td><td><img src="classpath:com/trolltech/images/mandelbrot_zoom3.png" /></td></tr>
</table></p>
<p>Similarly, when the user scrolls, the previous pixmap is scrolled immediately, revealing unpainted areas beyond the edge of the pixmap, while the image is rendered by the worker thread.</p>
<p><table align="center" cellpadding="2" cellspacing="1" border="0">
<tr valign="top" class="odd"><td><img src="classpath:com/trolltech/images/mandelbrot_scroll1.png" /></td><td><img src="classpath:com/trolltech/images/mandelbrot_scroll2.png" /></td><td><img src="classpath:com/trolltech/images/mandelbrot_scroll3.png" /></td></tr>
</table></p>
<p>The application consists of two classes:</p>
<ul>
<li><tt>RenderThread</tt> is a <tt>Thread</tt> subclass that renders the Mandelbrot set.</li>
<li><tt>Mandelbrot</tt> is a QWidget subclass that shows the Mandelbrot set on screen and lets the user zoom and scroll.</li>
</ul>
<a name="renderthread-class-implementation"></a>
<h2>RenderThread Class Implementation</h2>
<p>We'll start with the implementation of the <tt>RenderThread</tt> class:</p>
<pre>        private class RenderThread extends Thread {
            private double centerX;
            private double centerY;
            private double scaleFactor;
            private QSize resultSize;
            private boolean restart;

            final int ColormapSize = 512;
            int[] colormap = new int[ColormapSize];

            RenderThread() {
                restart = false;

                for (int i = 0; i &lt; ColormapSize; ++i) {
                    double wave = 380.0 + (i * 400.0 / ColormapSize);
                    colormap[i] = rgbFromWaveLength(wave);
                }
            }</pre>
<p>The class inherits <tt>Thread</tt> so that it gains the ability to run in a separate thread.</p>
<p>In the constructor, we initialize the <tt>restart</tt> and <tt>abort</tt> variables to <tt>false</tt>. These variables control the flow of the <tt>run()</tt> method. We also initialize the <tt>colormap</tt> array, which contains a series of RGB colors.</p>
<pre>            synchronized void render(double centerX, double centerY,
                                     double scaleFactor, QSize resultSize) {

                this.centerX = centerX;
                this.centerY = centerY;
                this.scaleFactor = scaleFactor;
                this.resultSize = resultSize;

                if (!isAlive()) {
                    start();
                } else {
                    restart = true;
                    notify();
                }
            }</pre>
<p>The <tt>render()</tt> method is called by the <tt>Mandelbrot</tt> whenever it needs to generate a new image of the Mandelbrot set. The <tt>centerX</tt>, <tt>centerY</tt>, and <tt>scaleFactor</tt> parameters specify the portion of the fractal to render; <tt>resultSize</tt> specifies the size of the resulting QImage.</p>
<p>The method stores the parameters in member variables. If the thread isn't already running, it starts it; otherwise, it sets <tt>restart</tt> to <tt>true</tt> (telling <tt>run()</tt> to stop any unfinished computation and start again with the new parameters) and wakes up the thread, which might be sleeping.</p>
<pre>            public void run() {
                QSize resultSize;
                double scaleFactor;
                double centerX;
                double centerY;

                while (true) {
                    synchronized (this) {
                        resultSize = this.resultSize;
                        scaleFactor = this.scaleFactor;
                        centerX = this.centerX;
                        centerY = this.centerY;
                    }</pre>
<p><tt>run()</tt> is quite a big method, so we'll break it down into parts.</p>
<p>The method body is an infinite loop which starts by storing the rendering parameters in local variables. As usual, we protect accesses to the member variables using the synchronized keyword. Storing the member variables in local variables allows us to minimize the amount of code that needs to be protected. This ensures that the main thread will never have to block for too long when it needs to access <tt>RenderThread</tt>'s member variables (e.g&#x2e;, in <tt>render()</tt>).</p>
<pre>                    int halfWidth = resultSize.width() / 2;
                    int halfHeight = resultSize.height() / 2;
                    QImage.Format format = QImage.Format.Format_RGB32;
                    QImage image = new QImage(resultSize, format);

                    final int NumPasses = 8;
                    int pass = 0;
                    while (pass &lt; NumPasses) {
                        final int MaxIterations = (1 &lt;&lt; (2 * pass + 6)) + 32;
                        final int Limit = 4;
                        boolean allBlack = true;

                        for (int y = -halfHeight; y &lt; halfHeight; ++y) {
                            if (restart)
                                break;
                            if (abort)
                                return;

                            double ay = centerY + (y * scaleFactor);

                            for (int x = -halfWidth; x &lt; halfWidth; ++x) {
                                double ax = centerX + (x * scaleFactor);
                                double a1 = ax;
                                double b1 = ay;
                                int numIterations = 0;

                                do {
                                    ++numIterations;
                                    double a2 = (a1 * a1) - (b1 * b1) + ax;
                                    double b2 = (2 * a1 * b1) + ay;
                                    if ((a2 * a2) + (b2 * b2) &gt; Limit)
                                        break;

                                    ++numIterations;
                                    a1 = (a2 * a2) - (b2 * b2) + ax;
                                    b1 = (2 * a2 * b2) + ay;
                                    if ((a1 * a1) + (b1 * b1) &gt; Limit)
                                        break;
                                } while (numIterations &lt; MaxIterations);

                                if (numIterations &lt; MaxIterations) {
                                    int index = numIterations % ColormapSize;
                                    image.setPixel(x + halfWidth, y + halfHeight,
                                                   colormap[index]);

                                    allBlack = false;
                                } else {
                                    image.setPixel(x + halfWidth, y + halfHeight,
                                                   0xff000000);
                                }
                            }
                        }
                        if (allBlack &amp;&amp; pass == 0) {
                            pass = 4;
                        } else {
                            synchronized (this) {
                            if (!restart) {
                                //renderedImage.emit(image, scaleFactor);
                                updatePixmap(image, scaleFactor);
                            }
                            }
                            ++pass;
                        }
                    }</pre>
<p>Then comes the core of the algorithm. Instead of trying to create a perfect Mandelbrot set image, we do multiple passes and generate more and more precise (and computationally expensive) approximations of the fractal.</p>
<p>If we discover inside the loop that <tt>restart</tt> has been set to <tt>true</tt> (by <tt>render()</tt>), we break out of the loop immediately, so that the control quickly returns to the very top of the outer loop and we fetch the new rendering parameters. Similarly, if we discover that <tt>abort</tt> has been set to <tt>true</tt> (by the <tt>Mandelbrot.closeEvent()</tt> method), we return from the method immediately, terminating the thread.</p>
<p>The core algorithm is beyond the scope of this tutorial.</p>
<pre>                    synchronized (this) {
                        if (!restart)
                            try {
                                wait();
                            } catch (InterruptedException event) {
                                event.printStackTrace();
                            }
                        restart = false;
                    }
                }
            }</pre>
<p>Once we're done with all the iterations, we call <tt>wait()</tt> to put the thread to sleep by calling, unless <tt>restart</tt> is <tt>true</tt>. There's no use in keeping a worker thread looping indefinitely while there's nothing to do.</p>
<pre>            int rgbFromWaveLength(double wave) {
                double red= 0.0;
                double green = 0.0;
                double blue = 0.0;

                if (wave &gt;= 380.0 &amp;&amp; wave &lt;= 440.0) {
                    red = -1.0 * (wave - 440.0) / (440.0 - 380.0);
                    blue = 1.0;
                } else if (wave &gt;= 440.0 &amp;&amp; wave &lt;= 490.0) {
                    green = (wave - 440.0) / (490.0 - 440.0);
                    blue = 1.0;
                } else if (wave &gt;= 490.0 &amp;&amp; wave &lt;= 510.0) {
                    green = 1.0;
                    blue = -1.0 * (wave - 510.0) / (510.0 - 490.0);
                } else if (wave &gt;= 510.0 &amp;&amp; wave &lt;= 580.0) {
                    red = (wave - 510.0) / (580.0 - 510.0);
                    green = 1.0;
                } else if (wave &gt;= 580.0 &amp;&amp; wave &lt;= 645.0) {
                    red = 1.0;
                    green = -1.0 * (wave - 645.0) / (645.0 - 580.0);
                } else if (wave &gt;= 645.0 &amp;&amp; wave &lt;= 780.0) {
                    red= 1.0;
                }

                double s = 1.0;
                if (wave &gt; 700.0)
                    s = 0.3 + 0.7 * (780.0 - wave) / (780.0 - 700.0);
                else if (wave &lt; 420.0)
                    s = 0.3 + 0.7 * (wave - 380.0) / (420.0 - 380.0);

                red = Math.pow(red * s, 0.8) * 255;
                green = Math.pow(green * s, 0.8) * 255;
                blue = Math.pow(blue * s, 0.8) * 255;

                QColor color = new QColor((int) red, (int) green, (int) blue);

                return color.rgb();
            }
        }</pre>
<p>The <tt>rgbFromWaveLength()</tt> method is a helper method that converts a wave length to a RGB value compatible with 32-bit QImages. It is called from the constructor to initialize the <tt>colormap</tt> array with pleasing colors.</p>
<a name="mandelbrot-class-implementation"></a>
<h2>Mandelbrot Class Implementation</h2>
<p>The <tt>Mandelbrot</tt> class uses <tt>RenderThread</tt> to draw the Mandelbrot set on screen.</p>
<pre>    public class Mandelbrot extends QWidget {

        private RenderThread thread = new RenderThread();
        private QImage pixmap = new QImage();
        private QPoint pixmapOffset = new QPoint();
        private QPoint lastDragPosition = new QPoint();
        private double centerX;
        private double centerY;
        private double pixmapScale;
        private double currentScale;

        private boolean abort = false;

        final double DefaultCenterX = -0.637011f;
        final double DefaultCenterY = -0.0395159f;
        final double DefaultScale = 0.00403897f;

        final double ZoomInFactor = 0.8f;
        final double ZoomOutFactor = 1 / ZoomInFactor;
        final int ScrollStep = 20;

        private Signal2&lt;QImage, Double&gt; renderedImage =
                new Signal2&lt;QImage, Double&gt;();</pre>
<p>The implementation starts with a few constants that we'll need later on. We also declare a signal: Whenever a thread is done rendering an image, it emits the <tt>renderedImage()</tt> signal.</p>
<pre>        public Mandelbrot() {
            this(null);
        }</pre>
<p>The interesting part of the constructor is QObject.connect() call. Although it looks like a standard signal-slot connection between two QObjects, because the signal is emitted in a different thread than the receiver lives in, the connection is effectively a queued connection. These connections are asynchronous (i.e&#x2e;, non-blocking), meaning that the slot will be called at some point after the <tt>emit</tt> statement. What's more, the slot will be invoked in the thread in which the receiver lives. Here, the signal is emitted in the worker thread, and the slot is executed in the GUI thread when control returns to the event loop.</p>
<pre>        public void paintEvent(QPaintEvent event) {
            QPainter painter = new QPainter();
            painter.begin(this);
            painter.setRenderHint(RenderHint.SmoothPixmapTransform);
            painter.fillRect(rect(), new QBrush(QColor.black));

            if (pixmap.isNull()) {
                String message = tr(&quot;Rendering initial image, please wait...&quot;);
                painter.setPen(QColor.white);
                painter.drawText(rect(), Qt.AlignmentFlag.AlignCenter.value(),
                                 message);
                painter.end();

                return;
            }</pre>
<p>In paintEvent(), we start by filling the background with black. If we have nothing yet to paint (<tt>pixmap</tt> is null), we print a message on the widget asking the user to be patient, returning from the method immediately.</p>
<pre>            if (currentScale == pixmapScale) {
                painter.drawImage(pixmapOffset, pixmap);
            } else {
                double scaleFactor = pixmapScale / currentScale;
                int newWidth = (int) (pixmap.width() * scaleFactor);
                int newHeight = (int) (pixmap.height() * scaleFactor);

                int newX = pixmapOffset.x() + (pixmap.width() - newWidth) / 2;
                int newY = pixmapOffset.y() + (pixmap.height() - newHeight) / 2;

                painter.save();
                painter.translate(newX, newY);
                painter.scale(scaleFactor, scaleFactor);

                QMatrix invertedMatrix = painter.worldMatrix().inverted();
                QRect exposed = invertedMatrix.mapRect(rect());
                exposed = exposed.adjusted(-1, -1, 1, 1);

                if(scaleFactor&gt;=0)
                    painter.drawImage(pixmapOffset, pixmap);
                else
                    painter.drawImage(exposed, pixmap, exposed);

                painter.restore();
            }</pre>
<p>If the pixmap has the right scale factor, we draw the pixmap directly onto the widget. Otherwise, we scale and translate the coordinate system before we draw the pixmap. By reverse mapping the widget's rectangle using the scaled painter matrix, we also make sure that only the exposed areas of the pixmap are drawn. The calls to QPainter.save() and QPainter.restore() make sure that any painting performed afterwards uses the standard coordinate system.</p>
<pre>            String text = tr(&quot;Use mouse wheel to zoom.&quot;)
                          + tr(&quot;Press and hold left mouse button to scroll.&quot;);
            QFontMetrics metrics = painter.fontMetrics();
            int textWidth = metrics.width(text);
            int offset = (width() - textWidth) / 2;

            painter.setPen(QPen.NoPen);
            painter.setBrush(new QColor(0, 0, 0, 127));
            painter.drawRect(offset - 5, 0, textWidth + 10, metrics.lineSpacing() + 5);
            painter.setPen(QColor.white);
            painter.drawText(offset, metrics.leading() + metrics.ascent(), text);
            painter.end();
        }</pre>
<p>At the end of the paint event handler, we draw a text string and a semi-transparent rectangle on top of the fractal.</p>
<pre>        public void resizeEvent(QResizeEvent event) {
            thread.render(centerX, centerY, currentScale, size());
        }</pre>
<p>Whenever the user resizes the widget, we call <tt>render()</tt> to start generating a new image, with the same <tt>centerX</tt>, <tt>centerY</tt>, and <tt>currentScale</tt> parameters but with the new widget size.</p>
<p>Notice that we rely on <tt>resizeEvent()</tt> being automatically called by Qt when the widget is shown the first time to generate the image the very first time.</p>
<pre>        protected void closeEvent(QCloseEvent event) {
            synchronized (thread) {
                abort = true;
                thread.notify();
            }
            super.closeEvent(event);
        }</pre>
<p>The <tt>closeEvent()</tt> method is reimplemented to receive the widget's close events because we want to ensure that the <tt>run()</tt> method stops running as soon as possible. This is done by setting <tt>abort</tt> to <tt>true</tt>, before passing the event to the base class event handler.</p>
<pre>        public void keyPressEvent(QKeyEvent event) {
            Qt.Key key = Qt.Key.resolve(event.key());
            switch (key) {
            case Key_Plus:
                zoom(ZoomInFactor);
                break;
            case Key_Minus:
                zoom(ZoomOutFactor);
                break;
            case Key_Left:
                scroll(-ScrollStep, 0);
                break;
            case Key_Right:
                scroll(+ScrollStep, 0);
                break;
            case Key_Down:
                scroll(0, -ScrollStep);
                break;
            case Key_Up:
                scroll(0, +ScrollStep);
                break;
            default:
                super.keyPressEvent(event);
            }
        }</pre>
<p>The key press event handler provides a few keyboard bindings for the benefit of users who don't have a mouse. The <tt>zoom()</tt> and <tt>scroll()</tt> methods will be covered later.</p>
<pre>        public void wheelEvent(QWheelEvent event) {
            int numDegrees = event.delta() / 8;
            double numSteps = numDegrees / 15.0f;
            zoom(Math.pow(ZoomInFactor, numSteps));
        }</pre>
<p>The wheel event handler is reimplemented to make the mouse wheel control the zoom level. QWheelEvent.delta() returns the angle of the wheel mouse movement, in eights of a degree. For most mice, one wheel step corresponds to 15 degrees. We find out how many mouse steps we have and determine the zoom factor in consequence. For example, if we have two wheel steps in the positive direction (i.e&#x2e;, +30 degrees), the zoom factor becomes <tt>ZoomInFactor</tt> to the second power, i.e&#x2e; 0.8 * 0.8 = 0.64.</p>
<pre>        public void mousePressEvent(QMouseEvent event) {
            if (event.button() == Qt.MouseButton.LeftButton)
                lastDragPosition = event.pos();
        }</pre>
<p>When the user presses the left mouse button, we store the mouse pointer position in <tt>lastDragPos</tt>.</p>
<pre>        public void mouseMoveEvent(QMouseEvent event) {
            if (event.buttons().isSet(Qt.MouseButton.LeftButton)) {
                pixmapOffset.add(event.pos());
                pixmapOffset.subtract(lastDragPosition);

                lastDragPosition = event.pos();
                update();
            }
        }</pre>
<p>When the user moves the mouse pointer while the left mouse button is pressed, we adjust <tt>pixmapOffset</tt> to paint the pixmap at a shifted position and call QWidget.update() to force a repaint.</p>
<pre>        public void mouseReleaseEvent(QMouseEvent event) {
            if (event.button() == Qt.MouseButton.LeftButton) {
                pixmapOffset.add(event.pos());
                pixmapOffset.subtract(lastDragPosition);
                lastDragPosition = new QPoint();

                int deltaX = (width() - pixmap.width()) / 2 - pixmapOffset.x();
                int deltaY = (height() - pixmap.height()) / 2 - pixmapOffset.y();
                scrollImage(deltaX, deltaY);
            }
        }</pre>
<p>When the left mouse button is released, we update <tt>pixmapOffset</tt> just like we did on a mouse move and we reset <tt>lastDragPosition</tt> to a default value. Then, we call <tt>scroll()</tt> to render a new image for the new position. (Adjusting <tt>pixmapOffset</tt> isn't sufficient because areas revealed when dragging the pixmap are drawn in black.)</p>
<pre>        private void updatePixmap(QImage image, Double scaleFactor) {
            if (!lastDragPosition.isNull())
                return;
            pixmap = image;
            pixmapOffset = new QPoint();
            lastDragPosition = new QPoint();
            pixmapScale = scaleFactor;

            QApplication.invokeLater(new Runnable() {
                public void run() {
                    synchronized (thread) {
                        if(!abort)
                            update();
                    }
                }
            });
        }</pre>
<p>The <tt>updatePixmap()</tt> slot is invoked when the worker thread has finished rendering an image. We start by checking whether a drag is in effect and do nothing in that case. In the normal case, we store the image in <tt>pixmap</tt> and reinitialize some of the other members. At the end, we call QWidget.update() to refresh the display.</p>
<p>At this point, you might wonder why we use a QImage for the parameter and a QPixmap for the data member. Why not stick to one type? The reason is that QImage is the only class that supports direct pixel manipulation, which we need in the worker thread. On the other hand, before an image can be drawn on screen, it must be converted into a pixmap. It's better to do the conversion once and for all here, rather than in <tt>paintEvent()</tt>.</p>
<pre>        protected void zoom(double zoomFactor) {
            currentScale *= zoomFactor;
            update();
            thread.render(centerX, centerY, currentScale, size());
        }</pre>
<p>In <tt>zoom()</tt>, we recompute <tt>currentScale</tt>. Then we call QWidget.update() to draw a scaled pixmap, and we ask the worker thread to render a new image corresponding to the new <tt>currentScale</tt> value.</p>
<pre>        public void scrollImage(int deltaX, int deltaY) {
            centerX += deltaX * currentScale;
            centerY += deltaY * currentScale;
            update();
            thread.render(centerX, centerY, currentScale, size());
        }</pre>
<p><tt>scroll()</tt> is similar to <tt>zoom()</tt>, except that the affected parameters are <tt>centerX</tt> and <tt>centerY</tt>.</p>
<a name="the-main-method"></a>
<h2>The main() Method</h2>
<p>The application's multithreaded nature has no impact on its <tt>main()</tt> method, which is as simple as usual:</p>
<pre>        public static void main(String args[]) {
            QApplication.initialize(args);
            Mandelbrot mainWindow = new Mandelbrot();
            mainWindow.show();
            QApplication.exec();
        }
    }</pre>
</body>
</html>
